1. Field of the Invention
The present invention relates to data processing systems and more particularly to data processing systems which encounter conditional branch instructions in an instruction preprocessing unit which prefetches, predecodes, and queues multiple instructions for sequential presentation to an instruction execution unit.
2. Prior Art
The IBM System/370 Family of Computers defined by the System/370 Principles of Operations, Form No. GA22-7000, are required to execute conditional branch instructions. Conditional branch instructions specify a condition to be tested for, and the address of a new instruction to be executed if a specified condition is met. Otherwise, instruction processing continues in sequence from the conditional branch instruction. In high-performance, pipelined computers, an instruction preprocessing function (IPPF) may be used to prefetch instructions from main memory and prepare a plurality of them for sequential execution by an execution unit. When the IPPF decodes a conditional branch instruction, a preceding instruction which will establish the condition to be tested may not have been executed. It will therefore be uncertain as to whether the instruction identified by the address information of the branch instruction will in fact be executed. Some strategy must be adopted to allow the IPPF to continue prefetching of instructions from memory and predecoding of these instructions beyond the branch instruction to maintain the queue of instructions for presentation to the execution unit.
U.S. Pat. No. 3,418,638 assigned to the assignee of the present application, issued Dec. 24, 1968 to D. W. Anderson et al and entitled "Instruction Processing Unit For Program Branches" discloses the conditional branch handling mechanism of the IBM System/360 Model 90. Instructions were prefetched, predecoded and immediately transferred to a plurality of execution units whereby overlapped instruction processing and execution could be achieved. A complicated mechanism was provided for transferring conditional branch instructions to various execution units followed by further instructions which were especially marked as being conditional, and which may or may not be executed dependent upon the outcome of the conditional branch. The instruction unit contained only a single set of instruction buffers which limited the capability of the instruction unit to decode only a single conditional branch instruction and prefetch only a single target instruction stream.
U.S. Pat. No. 3,551,895 which is assigned to the assignee of the present application and which issued Dec. 29, 1970 to G. C. Driscoll, Jr., entitled "Look-Ahead Branch Detection System" discloses another high performance computer system for prefetching and predecoding instructions including conditional branch instructions. This patent discloses a requirement for a special instruction called an "Advance Branch" instruction which was utilized by an associative memory and look-ahead trees for prefetching target instruction streams when conditional branches were encountered.
Another prior, high-performance system, is the IBM System/370 Model 168 which includes an IPPF for prefetching and predecoding a plurality of instructions to be presented in sequence to an execution unit. In the System/370 Model 168-III Theory of Operations, Diagrams Manual (Vol. 2), I-Unit, Form No. SY22-6932-3, the IPPF mechanism is fully described. In this system, two separate instruction buffers are included such that prefetching and predecoding of instructions either from the instruction stream of a conditional branch instruction, or from the target instruction stream can be effected. A prediction is made during decode of conditional branch instructions as to whether or not the branch is likely to be successful or unsuccessful. Further decoding from either the original instruction stream or the target instruction stream will be effected based on this prediction, and preprocessed instructions will be buffered in a queue for sequential presentation to the execution unit. The success or failure of a condition tested will ultimately determine whether the previously decoded instructions are from the proper instruction stream. Since only two instruction buffers are provided, only the set or reset state of a trigger is required to control the proper gating of instructions to a decoding mechanism from the proper one of the two buffers.
The provision of only two instruction buffers in the System/370 Model 168, permits only a single conditonal branch instruction to be outstanding at any one time. If a second conditional branch instruction is detected in the instruction decoding mechanism, the IPPF mechanism must cease functioning until the first conditional branch is resolved, because a second target instruction stream may not be prefetched.